package com.leaf.spring.y201911.day19;

import java.util.ArrayList;
import java.util.List;

/**
 * 迷你版HashMap
 * 
 * @author gaowenjin
 *
 * @param <K>
 * @param <V>
 */
public class MyHashMap<K, V> implements MyMap<K, V> {

	// 数据初始化长度
	private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

	// 阈值比例
	private static final float DEFAULT_LOAD_FACTOR = 0.75F;

	private int defaultInitSize;
	private float defaultLoadFactor;

	// map当中entry的数量
	private int entryUseSize;

	// 数组
	private Entry[] table = null;

	// 默认构造方法
	public MyHashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

	public MyHashMap(int initialCapacity, float loadFactor) {

		if (initialCapacity < 0) {
			throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
		}

		if (loadFactor <= 0 || Float.isNaN(loadFactor))
			throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

		this.defaultInitSize = initialCapacity;
		this.defaultLoadFactor = loadFactor;

		table = new Entry[this.defaultInitSize];
	}

	@Override
	public V put(K k, V v) {

		V oldValue = null;

		// 是否需要扩容
		// 扩容完毕，需要重新散列
		if (entryUseSize >= defaultInitSize * defaultLoadFactor) {
			resize(2 * defaultInitSize);
		}

		// 得到hash值，计算出数组中的位置
		int index = hash(k) & (defaultInitSize - 1);

		// v不存在，直接放入
		if (table[index] == null) {
			table[index] = new Entry<K, V>(k, v, null);
			++entryUseSize;
		} else {
			// v存在，将v取出，放入新v
			Entry<K, V> entry = table[index];
			Entry<K, V> e = entry;
			while (e != null) {
				if (k == e.getKey() || k.equals(e.getKey())) {
					oldValue = e.value;
					e.value = v;
					return oldValue;
				}
				e = e.next;
			}
			table[index] = new Entry<>(k, v, entry);
			++entryUseSize;
		}
		return oldValue;
	}

	// 扩容
	private void resize(int newCapacity) {
		Entry<K, V>[] newTable = new Entry[newCapacity];
		// 改变了数组的大小
		defaultInitSize = newCapacity;
		entryUseSize = 0;
		rehash(newTable);
	}

	private void rehash(Entry<K, V>[] newTable) {

		// 得到原来老的Entry集合，注意遍历单链表
		List<Entry<K, V>> entryList = new ArrayList<>();
		for (Entry<K, V> entry : table) {
			while (entry != null) {
				entryList.add(entry);
				entry = entry.next;
			}
		}

		// 覆盖旧的引用
		table = newTable;

		// 重新HASH
		for (Entry<K, V> entry : entryList) {
			put(entry.getKey(), entry.getValue());
		}

	}

	@Override
	public V get(K k) {

		int index = hash(k) & (defaultInitSize - 1);

		if (table[index] == null) {
			return null;
		} else {
			Entry<K, V> entry = table[index];

			while (entry != null) {
				if (k == entry.getKey() || k.equals(entry.getKey())) {
					return entry.getValue();
				}
				entry = entry.next;
			}

		}

		return null;
	}

	private int hash(K k) {

		int hashCode = k.hashCode();
		hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
		return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);

	}

	class Entry<E, V> implements MyMap.Entry<K, V> {

		private K key;
		private V value;
		private Entry<K, V> next;

		public Entry() {

		}

		public Entry(K key, V value, Entry<K, V> next) {
			this.key = key;
			this.value = value;
			this.next = next;
		}

		@Override
		public K getKey() {
			return key;
		}

		@Override
		public V getValue() {
			return value;
		}

	}

}
